/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<string>> ans;

    bool check(const string &s)
    {
        int i = 0, j = s.size() - 1;
        while (i < j)
        {
            if (s[i] != s[j])
                return false;
            i++, --j;
        }
        return true;
    }

    void dfs(vector<int> &split_point, int pos, const int num_split_points, const string &s)
    {
        if (split_point.size() == 1)
        {
            int l = 0, r = split_point[0];
            if (!check(s.substr(l, r - l)))
                return;
        }
        if (split_point.size() >= 2)
        {
            int r = *(split_point.end() - 1);
            int l = *(split_point.end() - 2);
            if (!check(s.substr(l, r - l)))
                return;
        }

        if (split_point.size() == num_split_points)
        {
            if (*(split_point.end() - 1) != s.size())
                return;
            vector<string> res;
            int l = 0;
            for (int i = 0; i < num_split_points; i++)
            {
                int r = split_point[i];
                auto ss = s.substr(l, r - l);
                res.push_back(ss);
                l = r;
            }
            ans.push_back(res);
            return;
        }

        if (pos > s.size())
            return;
        dfs(split_point, pos + 1, num_split_points, s);
        split_point.push_back(pos);
        dfs(split_point, pos + 1, num_split_points, s);
        split_point.erase(split_point.end() - 1);
        return;
    }

    vector<vector<string>> partition(string s)
    {
        if (check(s))
        {
            ans.push_back({s});
        }
        for (int num_split_points = 2; num_split_points <= s.size(); num_split_points++)
        {
            vector<int> split_point;
            dfs(split_point, 1, num_split_points, s);
        }
        return ans;
    }
};

// int main()
// {
//     Solution().partition("cdd");
//     return 0;
// }
// @lc code=end
